import java.util.Arrays;
import java.util.Comparator;

/**
 * 剑指 Offer 45. 把数组排成最小的数
 * https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/
 * 进阶：快速排序、优先队列
 */
public class Solutions_Offer_45 {
    public static void main(String[] args) {
//        int[] nums = {10, 2};  // output: "102"
//        int[] nums = {3, 30, 34, 5, 9};  // output: "3033459"
        int[] nums = {0, 3, 0, 0, 3};  // output: "00033"

        String result = minNumber(nums);
        System.out.println(result);
    }

    public static String minNumber(int[] nums) {
        int len = nums.length;
        String[] strs = new String[len];
        for (int i = 0; i < len; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        StringBuilder sb = new StringBuilder();
        // 排序
        Arrays.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                // {10, 2} 比较字符串 "102" 与 "210"
                String s1 = o1 + o2;
                String s2 = o2 + o1;
                // 升序排列（前比后）
                return s1.compareTo(s2);
            }
        });
        for (String str : strs) {
            sb.append(str);
        }
        return sb.toString();
    }
}
